home *** CD-ROM | disk | FTP | other *** search
/ AI Game Programming Wisdom / AIGameProgrammingWisdom.iso / SourceCode / 11 Learning / 04 Mommersteeg / Predictors / IteratorList.h < prev    next >
Encoding:
C/C++ Source or Header  |  2001-09-30  |  13.2 KB  |  390 lines
  1. //----------------------------------------------------------------------------------------------
  2. // Sequential Prediction Demo: The positioning pattern
  3. //
  4. // Author:  Fri Mommersteeg
  5. // Date:    10-09-2001
  6. // File:    IteratorList.h
  7. //----------------------------------------------------------------------------------------------
  8.  
  9. //----------------------------------------------------------------------------------------------
  10. //    The IteratorList is a double linked list that uses an implicit itorator.
  11. //
  12. //    This data structure has all the benefits of a list, and adds O(1) indexing for
  13. //    sequential iterations.
  14. //----------------------------------------------------------------------------------------------
  15.  
  16. #ifndef __ITERATORLIST_H
  17. #define __ITERATORLIST_H
  18.  
  19. //----------------------------------------------------------------------------------------------
  20. // CListContainer: An entry in the list; it contains forward and backward links
  21. //----------------------------------------------------------------------------------------------
  22.  
  23. template <class TData>
  24. class CListContainer {
  25. public:
  26.     TData            m_data;
  27.     void *            m_pNext;
  28.     void *            m_pPrevious;
  29. };
  30.  
  31.  
  32. //----------------------------------------------------------------------------------------------
  33. // CIterator: A list iterator
  34. //----------------------------------------------------------------------------------------------
  35.  
  36. template <class TData>
  37. class CIterator {
  38. public:
  39.     // constructor method
  40.                                 CIterator() { m_pContainer = NULL; }
  41.  
  42. public:
  43.     // iterator setup and maintenance routines
  44.     void                        AttachToList(CListContainer <TData> * pContainer, int iIndex = 0);
  45.     void                        SetIndex(int iIndex) { m_index = iIndex; }
  46.     int                         GetIndex() const { return m_index; }
  47.  
  48. public:
  49.     // iterator manipulation
  50.     BOOL                        Next();
  51.     BOOL                        Previous();
  52.     CListContainer <TData> *    GetContainer() const;
  53.  
  54. protected:
  55.     CListContainer <TData> *    m_pContainer;
  56.     int                            m_index;
  57. };
  58.  
  59.  
  60. //----------------------------------------------------------------------------------------------
  61. // CIteratorList: List template with implicit iterator
  62. //----------------------------------------------------------------------------------------------
  63.  
  64. template <class TData>
  65. class CIteratorList {
  66. public:
  67.     // construction & destruction methods
  68.                                 CIteratorList();
  69.                                 ~CIteratorList();
  70.  
  71. public:
  72.     // list manipulation methods
  73.     BOOL                        AddHead(TData data);
  74.     BOOL                        AddTail(TData data);
  75.     BOOL                        InsertAt(int iIndex, TData data);
  76.     void                        RemoveHead();
  77.     void                        RemoveTail();
  78.     void                        RemoveAt(int iIndex);
  79.     void                        RemoveAll();
  80.  
  81. public:
  82.     // overloaded operators
  83.     const TData                    operator[](int iIndex) const;
  84.     TData &                        operator[](int iIndex);
  85.  
  86. public:
  87.     // get methods
  88.     inline TData &                GetHead() const { assert(m_nSize > 0); return m_pHead->m_data; }
  89.     inline TData &                GetTail() const { assert(m_nSize > 0); return m_pTail->m_data; }
  90.     int                            GetSize() const { return m_nSize; }
  91.  
  92. protected:
  93.     CListContainer <TData> *    GetContainer(int iIndex);
  94.     CListContainer <TData> *    MoveIterator(CIterator <TData> * pIterator, int iTargetIndex);
  95.  
  96. protected:
  97.     CListContainer <TData> *    m_pHead;
  98.     CListContainer <TData> *    m_pTail;
  99.     CIterator <TData>            m_itLastAccessPosition;
  100.     int                            m_nSize;
  101. };
  102.  
  103. //----------------------------------------------------------------------------------------------
  104. // AttachToList(): attaches the iterator to a certain container in the list
  105. //----------------------------------------------------------------------------------------------
  106.  
  107. template <class TData>
  108. void CIterator<TData>::AttachToList(CListContainer <TData> * pContainer, int iIndex) {
  109.     assert( pContainer != NULL );
  110.     m_pContainer = pContainer;
  111.     m_index = iIndex;
  112. }
  113.  
  114. //----------------------------------------------------------------------------------------------
  115. // Next(): moves the iterator to the next node in the list
  116. //----------------------------------------------------------------------------------------------
  117.  
  118. template <class TData>
  119. BOOL CIterator<TData>::Next() {
  120.     assert( m_pContainer != NULL );
  121.     if (m_pContainer->m_pNext != NULL) {
  122.         m_pContainer = (CListContainer <TData> *) m_pContainer->m_pNext;
  123.         m_index++;
  124.         return TRUE;
  125.     }
  126.     return FALSE;
  127. }
  128.  
  129. //----------------------------------------------------------------------------------------------
  130. // Previous(): moves the iterator to the previous node in the list
  131. //----------------------------------------------------------------------------------------------
  132.  
  133. template <class TData>
  134. BOOL CIterator<TData>::Previous() {
  135.     assert( m_pContainer != NULL );
  136.     if (m_pContainer->m_pPrevious != NULL) {
  137.         m_pContainer = (CListContainer <TData> *) m_pContainer->m_pPrevious;
  138.         m_index--;
  139.         return TRUE;
  140.     }
  141.     return FALSE;
  142. }
  143.  
  144. //----------------------------------------------------------------------------------------------
  145. // GetContainer(): returns the container that is currently selected by the iterator
  146. //----------------------------------------------------------------------------------------------
  147.  
  148. template <class TData>
  149. CListContainer <TData> * CIterator<TData>::GetContainer() const {
  150.     assert( m_pContainer != NULL );
  151.     return m_pContainer;
  152. }
  153.  
  154. //----------------------------------------------------------------------------------------------
  155. // CIteratorList(): constructor
  156. //----------------------------------------------------------------------------------------------
  157.  
  158. template <class TData>
  159. CIteratorList<TData>::CIteratorList() {
  160.     m_pHead = NULL;
  161.     m_pTail = NULL;
  162.     m_nSize = 0;
  163. }
  164.  
  165. //----------------------------------------------------------------------------------------------
  166. // ~CIteratorList(): destructor
  167. //----------------------------------------------------------------------------------------------
  168.  
  169. template <class TData>
  170. CIteratorList<TData>::~CIteratorList() {
  171.     RemoveAll();
  172. }
  173.  
  174. //----------------------------------------------------------------------------------------------
  175. // AddHead(): adds an element to the head of the list
  176. //----------------------------------------------------------------------------------------------
  177.  
  178. template <class TData>
  179. BOOL CIteratorList<TData>::AddHead(TData data) {
  180.     return InsertAt(0, data);
  181. }
  182.  
  183. //----------------------------------------------------------------------------------------------
  184. // AddTail(): adds an element to the tail of the list
  185. //----------------------------------------------------------------------------------------------
  186.  
  187. template <class TData>
  188. BOOL CIteratorList<TData>::AddTail(TData data) {
  189.     return InsertAt(m_nSize, data);
  190. }
  191.  
  192. //----------------------------------------------------------------------------------------------
  193. // InsertAt(): inserts an element at the specified position in the list
  194. //----------------------------------------------------------------------------------------------
  195.  
  196. template <class TData>
  197. BOOL CIteratorList<TData>::InsertAt(int iIndex, TData data) {
  198.     assert( iIndex >= 0 && iIndex <= m_nSize);
  199.  
  200.     // create new container
  201.     CListContainer <TData> * pContainer = new CListContainer <TData>;
  202.     if (pContainer == NULL) {
  203.         return FALSE;
  204.     }
  205.     pContainer->m_data = data;
  206.  
  207.     if (iIndex < m_nSize) {
  208.         // insert item in list
  209.         CListContainer <TData> * pReplace;
  210.         pReplace = GetContainer(iIndex);
  211.  
  212.         pContainer->m_pNext = (void *)pReplace;
  213.         pContainer->m_pPrevious = pReplace->m_pPrevious;
  214.         pReplace->m_pPrevious = (void *)pContainer;
  215.  
  216.         if (pContainer->m_pPrevious != NULL) {
  217.             CListContainer <TData> * pPrevious;
  218.             pPrevious = (CListContainer <TData> *) (pContainer->m_pPrevious);
  219.             pPrevious->m_pNext = (void *)pContainer;
  220.         } else {
  221.             m_pHead = pContainer;
  222.         }
  223.     } else {
  224.         // add item to end of list
  225.         pContainer->m_pNext = NULL;
  226.         pContainer->m_pPrevious = (void *)m_pTail;
  227.         if (m_pTail != NULL) {
  228.             m_pTail->m_pNext = (void *)pContainer;
  229.         } else {
  230.             m_pHead = pContainer;
  231.         }
  232.         m_pTail = pContainer;
  233.     }
  234.  
  235.     // move lap iterator
  236.     m_itLastAccessPosition.AttachToList(pContainer, iIndex);
  237.  
  238.     m_nSize++;
  239.     return TRUE;
  240. }
  241.  
  242. //----------------------------------------------------------------------------------------------
  243. // RemoveHead(): removes the element at the head of the list
  244. //----------------------------------------------------------------------------------------------
  245.  
  246. template <class TData>
  247. void CIteratorList<TData>::RemoveHead() {
  248.     RemoveAt(0);
  249. }
  250.  
  251. //----------------------------------------------------------------------------------------------
  252. // RemoveTail(): removes the element at the tail of the list
  253. //----------------------------------------------------------------------------------------------
  254.  
  255. template <class TData>
  256. void CIteratorList<TData>::RemoveTail() {
  257.     RemoveAt(m_nSize-1);
  258. }
  259.  
  260. //----------------------------------------------------------------------------------------------
  261. // RemoveAt(): removes the element at the specified position in the list
  262. //----------------------------------------------------------------------------------------------
  263.  
  264. template <class TData>
  265. void CIteratorList<TData>::RemoveAt(int iIndex) {
  266.     assert( iIndex >= 0 && iIndex < m_nSize);
  267.  
  268.     CListContainer <TData> * pRemove, * pNext, * pPrevious;
  269.     pRemove = GetContainer(iIndex);
  270.     pNext = (CListContainer <TData> *) (pRemove->m_pNext);
  271.     pPrevious = (CListContainer <TData> *) (pRemove->m_pPrevious);
  272.  
  273.     if (pPrevious != NULL) {
  274.         pPrevious->m_pNext = (void *)pNext;
  275.     } else {
  276.         m_pHead = pNext;
  277.     }
  278.  
  279.     if (pNext != NULL) {
  280.         pNext->m_pPrevious = (void *)pPrevious;
  281.     } else {
  282.         m_pTail = pPrevious;
  283.     }
  284.  
  285.     // release container
  286.     delete pRemove;
  287.  
  288.     // update lap iterator index if necessary
  289.     int iLapIndex = m_itLastAccessPosition.GetIndex();
  290.     if (iIndex <= iLapIndex) {
  291.         m_itLastAccessPosition.SetIndex(iLapIndex+1);
  292.     }
  293.  
  294.     m_nSize--;
  295. }
  296.  
  297. //----------------------------------------------------------------------------------------------
  298. // RemoveAll(): removes all elements from the list
  299. //----------------------------------------------------------------------------------------------
  300.  
  301. template <class TData>
  302. void CIteratorList<TData>::RemoveAll() {
  303.     while (m_pHead != NULL) {
  304.         CListContainer <TData> * pNext = (CListContainer <TData> *) m_pHead->m_pNext;
  305.         delete m_pHead;
  306.         m_pHead = pNext;
  307.     }
  308.     m_pTail = NULL;
  309.     m_nSize = 0;
  310. }
  311.  
  312. //----------------------------------------------------------------------------------------------
  313. // GetContainer(): returns the container at the specified position in the list
  314. //----------------------------------------------------------------------------------------------
  315.  
  316. template <class TData>
  317. CListContainer <TData> * CIteratorList<TData>::GetContainer(int iIndex) {
  318.     CIterator <TData> itHead, itTail;
  319.     int distHead, distTail, distLap;
  320.  
  321.     itHead.AttachToList(m_pHead, 0);
  322.     itTail.AttachToList(m_pTail, m_nSize-1);
  323.  
  324.     distHead = iIndex;
  325.     distTail = m_nSize - 1 - iIndex;
  326.     distLap = abs(iIndex - m_itLastAccessPosition.GetIndex());
  327.  
  328.     if (distHead < distTail) {
  329.         if (distHead < distLap) {
  330.             // distHead is the nearest to target distance
  331.             m_itLastAccessPosition = itHead;
  332.             return MoveIterator(&itHead, iIndex);
  333.         } else {
  334.             // distLap is the nearest to target distance
  335.             return MoveIterator(&m_itLastAccessPosition, iIndex);
  336.         }
  337.     } else {
  338.         if (distTail < distLap) {
  339.             // distTail is the nearest to target distance
  340.             m_itLastAccessPosition = itTail;
  341.             return MoveIterator(&itTail, iIndex);
  342.         } else {
  343.             // distLap is the nearest to target distance
  344.             return MoveIterator(&m_itLastAccessPosition, iIndex);
  345.         }
  346.     }
  347. }
  348.  
  349. //----------------------------------------------------------------------------------------------
  350. // operator[](): returns the element at the specified position in the list (constant)
  351. //----------------------------------------------------------------------------------------------
  352.  
  353. template <class TData>
  354. const TData    CIteratorList<TData>::operator[](int iIndex) const {
  355.     assert(iIndex >= 0 && iIndex < m_nSize);
  356.  
  357.     CListContainer <TData> * pContainer;
  358.     pContainer = GetContainer(iIndex);
  359.     return pContainer->m_data;
  360. }
  361.  
  362. //----------------------------------------------------------------------------------------------
  363. // operator[](): returns the element at the specified position in the list (reference)
  364. //----------------------------------------------------------------------------------------------
  365.  
  366. template <class TData>
  367. TData &    CIteratorList<TData>::operator[](int iIndex) {
  368.     assert(iIndex >= 0 && iIndex < m_nSize);
  369.  
  370.     CListContainer <TData> * pContainer;
  371.     pContainer = GetContainer(iIndex);
  372.     return pContainer->m_data;
  373. }
  374.  
  375. //----------------------------------------------------------------------------------------------
  376. // MoveIterator(): Moves an iterator to the specified target index
  377. //----------------------------------------------------------------------------------------------
  378.  
  379. template <class TData>
  380. CListContainer <TData> * CIteratorList<TData>::MoveIterator(CIterator <TData> * pIterator, int iTargetIndex) {
  381.     if (pIterator->GetIndex() < iTargetIndex) {
  382.         while (pIterator->GetIndex() != iTargetIndex) pIterator->Next();
  383.     } else {
  384.         while (pIterator->GetIndex() != iTargetIndex) pIterator->Previous();
  385.     }
  386.     return pIterator->GetContainer();
  387. }
  388.  
  389. //----------------------------------------------------------------------------------------------
  390. #endif // __ITERATORLIST_H